#include <iostream>
#include <vector>
using namespace std;

/***
 * 给你一个下标从 0 开始的整数数组 stones
 * 数组中的元素 严格递增 ，表示一条河中石头的位置。
 * 一只青蛙一开始在第一块石头上，它想到达最后一块石头，
 * 然后回到第一块石头。同时每块石头 至多 到达 一次。
 * 一次跳跃的 长度 是青蛙跳跃前和跳跃后所在两块石头之间的距离。
 * 更正式的，如果青蛙从 stones[i] 跳到 stones[j] ，
 * 跳跃的长度为|stones[i] - stones[j]| 。
 * 一条路径的 代价 是这条路径里的 最大跳跃长度 。
 * 请你返回这只青蛙的 最小代价 。
 * 
 * 输入：stones = [0,2,5,6,7]
 * 输出：5
 * 解释：上图展示了一条最优路径。
 * 这条路径的代价是 5 ，是这条路径中的最大跳跃长度。
 * 无法得到一条代价小于 5 的路径，我们返回 5 。
 * 
 * 
 * 输入：stones = [0,3,9]
 * 输出：9
 * 解释：
 * 青蛙可以直接跳到最后一块石头，然后跳回第一块石头。
 * 在这条路径中，每次跳跃长度都是 9 。所以路径代价是 max(9, 9) = 9 。
 * 这是可行路径中的最小代价。
 * 
 * 解题思路：
 * 思路一：贪心算法
 * 
 * 贪心算法：
 * c++中，贪心算法是一种在每一步选择中都采取当前状态下的最优解的选择
 * 从而希望导致结果时全局最优解的算法。贪心算法通常用来解决优化问题
 * 尤其是具有“贪心选择性质”时，即局部最优解能够推导出全局最优解
 * 
 * *贪心算法的特点：
 * 1.局部最优解：在每一步选择中都是当前情况下的最优选项，这种选择通常
 * 是基于某种贪心准则，例如选择、最大值、最小值、或者接近目标值的选项
 * 例如：在此题中我们可以将一只青蛙来回跳跃想象为两只青蛙分别按奇数和
 * 偶数的石头进行跳跃这样的代价一定最小
 * 
 * 2.逐步构建解：贪心算法为从局部最优解推导出全局最优解，逐步构建出最优解
 * 
 * 3.不回朔：贪心算法一旦做出选择选择不会回头去检查之前的决策是否优化
 * 导致贪心算法通常不能考虑出所有解的可能性，而是直接去寻找最优解
 * 
 * 思路二：二分查找 + 贪心算法
 * 根据题目意思，最大路径为直接从0跳跃到最后一个石头然后跳回，而优化后的
 * 算法就是在寻找中间的石头，我们可以推理出：
 * 有两个石头直接进行两次跳跃就行；
 * 有三个石头我们虽然可以借用中间的石头一次，但是代价还是那么大
 * 有四个石头我们就可以实现从1->4->3->2->1到1->3->4->2->1这样一个过程
 * 由此类推
 *   
 * 
 */

//思路一：直接运用贪心算法
class Solution_1 {
public:
    int maxJump(vector<int>& stones) {
        if(stones.size() == 2) {
            return stones.back() - stones[0];
        }
        int res = max(stones[1], stones[2]);
        for(int i = 1; i + 2 < stones.size(); i += 2) {
            res = max(res, stones[i + 2] - stones[i]);
        }

        for(int i = 2; i + 2 < stones.size(); i += 2) {
            res = max(res, stones[i + 2] - stones[i]);
        }
        return res;
    }
};

//思路二：二分查找 + 贪心算法
class Solution_2 {
public:
    bool check(int mid, vector<int>& m) {
        vector<bool> st(m.size(), false);
        for(int i = 0, j = 1; j < m.size(); j++) {
            while(j < m.size() && m[j] - m[i] <= mid) j++;
            st[j - 1] = true;
            i = j - 1;
        }

        st[m.size() - 1] = false;
        for(int i = 0, j = 1; j < m.size(); j++) {
            while(j < m.size() && st[j]) j++;
            if(m[j] - m[i] > mid){
                return false;
            }
            i = j;
        }
        return true;
    }

    int maxJump(vector<int>& stones) {
        //初始化左右指针的位置
        int l = 0;
        int r = stones.back();
        while(l < r) {
            //下面mid的赋值一般用于二分查找
            int mid = l + r >> 1;
            if(check(mid, stones)) r = mid;
            else l = mid + l; 

        }
        return r;
    }
};

int main()
{
    vector<int> stones = {0, 2, 5, 6, 7};
    Solution_2 s2;
    cout << s2.maxJump(stones) << endl;
    return 0;
}
